更多的練習

Exercise D5-1

前一天 的 foldRight 是從 List 的最右邊往左推進，想當然爾，當然也有從左邊開始的 foldLeft，

也剛好 foldRitht 並不是 tail-recursive，所以在極端情況下可能會發生 StackOverflowError，而 foldLeft 在實作上是可以符合 tail-recursive，就來試著練習吧！

import scala.annotation.tailrec

@tailrec
def foldLeft[A, B](as: List[A], z: B, f: (B, A) => B): B

tail-recursive 是以一個不同的方式來執行 recursive function，它的最後一個操作是呼叫自己，而不會有其它操作，當 Scala 編譯器檢測到 function 是 tail-recursive 時，編譯器會重寫 JVM bytecode，使其能重用 function 的 stack frame，

然後在程式中，我們可以用 @tailrec annotation 來標註某一 function 為 tail-recursive，若 function 不是 tail-recursive，編譯過程中會報錯，

所以這裡有個重點是 呼叫自己，前一天的 foldRight 就不符合這個條件，其 Cons 下的最後一個操作是調用 f，而不是直接呼叫自己。

  def foldRight[A, B](as: List[A], z: B, f: (A, B) => B): B = as match
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z, f))

Exercise D5-2

使用 foldLeft 來實現 function reverse，此 function 能反轉 List 的順序，例如 List(1, 2, 3) 能變成 List(3, 2, 1)。

def reverse[A](as: List[A]): List[A]

Exercise D5-3

使用 foldRight 來實現 Day 4 提到的 function append 。

def appendViaFoldRight[A](a1: List[A], a2: List[A]): List[A]

Exercise D5-4

使用 foldRight 來實現 function map，此 function 能修改 List 中的每個元素。

def map[A, B](l: List[A], f: A => B): List[B]

Scala 原生的 List 庫

List 在原生的 Scala 基礎庫下已經有支援，這裡是 API 連結，我們在之後所有有講到 List 的地方，都會泛指原生庫下的 List，

在 List 底下已經定義好許多好用的方法，也包含我們上面所練習的那些，

def take(n: Int): List[A] // 取得 List 的前 n 個元素
def exists(p: A => Boolean): Boolean // 看某個元素是否存在於 List 中
def takeWhile(p: A => Boolean): List[A] // 取得 List 前面所有符合條件的元素，直到某個元素不符合

Scala 原生 List 跟我們自定義 List 最大的差別就是，原生 List 使用 :: 來表示 Cons，所以 Cons(1, Cons(2, Nil)) 會等於 1 :: 2 :: Nil，

在 pattern match 時我們可以用 case h :: t 來表示 case Cons(h, t)，來避免我們使用巢狀結構來表達比較複雜的資料，例如可以用 h :: h2 :: t 來從 List 中提取前 2 個值。

在 Scala 中，若看到表達式中含有 : 符號，通常代表右邊的變數為主體，例如 h :: t，實際上是 t.::(h)。

Trees

List 是一個 ADT (algebraic data type 代數資料型態) 的範例，ADT 就是某種組合型態，由一個或多個資料建構器 (data constructors) 來定義，而每一個資料建構器也都能包含 1 到 多個參數，2 種常見的 ADT 類型為 product 和 sum，這個 文件 裡頭有更詳細的解釋。

product 類型範例：Tuple

Scala 中使用 ("Steven", 35) 來表達 (String, Int)，然後我們可以用 _ 來取得特定位置的值，目前 Tuple 型態 支援到 22 個值。

scala> val a = ("Steven", 35)
val a: (String, Int) = (Steven,35)

scala> a._1
Steven

scala> a._2
35

sum 類型範例：List, Tree

除了 List 以外，ADT 也能用來定義其它資料結構，例如 Binary Tree，

enum Tree[+A]:
  case Leaf(value: A)
  case Branch(left: Tree[A], right: Tree[A])

這裡我們一樣也可以用超好用的 pattern match 來操作 Tree。

Exercise D5-5

使用 pattern match 實作 function size，來計算 Tree 中節點數量 (Branch 和 Leaf)。

  def size[A](t: Tree[A]): Int 

總結

我們透過自行實做 List 來了解 functional 資料結構 (functional data structure)，它就是只使用 pure function 來做事的資料結構，而其重點就是 不可變 (immutable) 和 資料分享 (data sharing)，透過 ADT 定義好資料結構後，就可以用 pattern match 和遞迴來遍歷資料，然後完成所有相關操作。

Day 5 - Exercise answer